package cn.summit;

/**
 * @author summit
 * @since 2021/8/14 20:58
 */
public class 两数相加 {

	public static void main(String[] args) {
		ListNode l1 = new ListNode(2);
		l1.next = new ListNode(4);
		l1.next.next = new ListNode(3);

		ListNode l2 = new ListNode(5);
		l2.next = new ListNode(6);
		l2.next.next = new ListNode(4);

		ListNode l3 = new ListNode(9);
		l3.setNext(9).setNext(9).setNext(9).setNext(9).setNext(9).setNext(9);
		ListNode l4 = new ListNode(9);
		l4.setNext(9).setNext(9).setNext(9);

		ListNode listNode = addTwoNumbers(l3, l4);

		System.out.println(listNode);
	}

	private static ListNode head;

	private static ListNode tail;

	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		// 进位
		int extra = 0;
		while (true) {
			int sum = extra;
			extra = 0;
			if (l1 == null && l2 == null) {
				if (sum > 0) {
					addNode(sum);
				}
				break;
			}
			if (l1 != null) {
				sum += l1.val;
			}
			if (l2 != null) {
				sum += l2.val;
			}
			if (sum >= 10) {
				extra = sum / 10;
				sum = sum % 10;
			}
			addNode(sum);

			if (l1 != null) {
				l1 = l1.next;
			}

			if (l2 != null) {
				l2 = l2.next;
			}
		}


		return head;
	}

	public static void addNode(int value) {
		if (head == null) {
			tail = head = new ListNode(value);
			return;
		}
		tail.next = new ListNode(value);
		tail = tail.next;
	}

	static class ListNode {
		int val;

		ListNode next;

		public int getVal() {
			return val;
		}

		public void setVal(int val) {
			this.val = val;
		}

		public ListNode getNext() {
			return next;
		}

		public ListNode setNext(int val) {
			this.next = new ListNode(val);
			return this.next;
		}

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}
}
